package sjjg.tree;

public class MinPriorityQueue<T extends Comparable> {
    private T[] maxQueue;
    private int N;
    public MinPriorityQueue(int capacity){
        maxQueue=(T[])new Comparable[capacity+1];
        N=0;
    }
    public boolean less(int index1,int index2){
        return maxQueue[index1].compareTo(maxQueue[index2])<0;
    }
    public void exchange(int index1,int index2){
        T temp;
        temp=maxQueue[index1];
        maxQueue[index1]=maxQueue[index2];
        maxQueue[index2]=temp;
    }
    public T delMin(){
        exchange(1,N);
        N--;
        sink(1);
        return maxQueue[N+1];
    }
    public void insert(T t){
        maxQueue[++N]=t;
        swim(N);
    }
    public void swim(int k){
           while (k>1){
                 if(less(k,k/2)){
                     exchange(k,k/2);
                 }else {
                     break;
                 }
                 k=k/2;
           }
    }
    public void sink(int k){
         int min=0;
         while (2*k<=N){
               if(2*k+1<=N){
                   if(less(2*k,2*k+1)){
                       min=2*k;
                   }else {
                       min=2*k+1;
                   }
               }else {
                   min=2*k;
               }
               if(less(k,min)){
                   break;
               }
               exchange(k,min);
               k=min;
         }
    }
    public int size(){
        return N;
    }
    public boolean isEmpty(){
        return N==0;
    }

    public static void main(String[] args) {
        MinPriorityQueue<String> maxPriorityQueue = new MinPriorityQueue<>(10);

        maxPriorityQueue.insert("B");
        maxPriorityQueue.insert("E");
        maxPriorityQueue.insert("A");
        maxPriorityQueue.insert("F");
        maxPriorityQueue.insert("C");
        maxPriorityQueue.insert("D");
        maxPriorityQueue.insert("G");
        maxPriorityQueue.insert("H");
        maxPriorityQueue.insert("I");
        while (!maxPriorityQueue.isEmpty()){
            String integer = maxPriorityQueue.delMin();
            System.out.print(integer+" ");
        }
    }
}
